2 有限オ トマトン (2) 2. 有限オートマトン (2):
( テキスト 2.3.5~2.3.7,2.5)
( , )
前回の復習
– DFA A D =(Q D ,Σ,δ D ,q D ,F D ) によって受理される言語 L(A D )={ w | δ D ^ (q D ,w) ∈ F D }
δ D : Q × Σ→Q
次の状態はいつでも一意的に決まる– NFA A N =(Q N ,Σ,δ N ,q N ,F N ) によって受理される言語 L(A N )={ w | δ N ^ (q N ,w)∩F N ≠Φ}
L(A N ) { w | δ N (q N ,w)∩F N ≠Φ}
δ N : Q × Σ→2 Q
次の状態は一意的に決まらず、複数の状態の集合となる
2. 有限オートマトン (2)
2.3.5. 決定性と非決定性の有限オートマトン
の等価性
定理 : NFA で受理できる言語のクラスと、 DFA で受理で きる言語のクラスは一致する。
おまけ：‘集合の集合’のことは特にク ラス
(Class)
または族(Family)
と呼ぶ。2. 有限オートマトン (2)
2.3.5. 決定性と非決定性の有限オートマトンの
等価性
証明 : NFA で受理できる言語のクラス N と、 DFA で受理でき る言語のクラス D が一致することを示す。
• D ⊆ N
は定義より明らかなので、N ⊆ D
を示せばよい。•
任意の言語L ∈ N
がL ∈ D
となることを示せばよい。ある言語 が であ たとする このとき を受理す ある言語 L が L ∈ N であったとする。このとき、 L を受理す る NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A と同じ言語を受理する DFA A ’ を構成する
A L と同じ言語を受理する DFA A L ’ を構成する。
2. 有限オートマトン (2)
証明 : NFA で受理できる言語のクラス N と、 DFA で受理できる 言語のクラス D が一致することを示す
言語のクラス D が一致することを示す。
L ∈ N を受理する NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A と同じ言語を受理する DFA A ’ を構成する A L と同じ言語を受理する DFA A L を構成する。
証明の直感的アイデア：
証明の直感的アイデア：
•DFA は状態がいつも 1 つだけ決まっている。
•NFA は状態の集合が入力に応じて変化する。 変 す
→NFA の状態の集合を DFA の 1 つの集合とみなす !!
2. 有限オートマトン (2)
例 : q
1 q 2
0,1 0,1
0 0
δ 0 1
q {q q } {q q }
q 0
q 3 q 4
1 1
q 0 {q 0 ,q 1 } {q 0 ,q 3 } q 1 {q 2 } Φ
q 2 {q 2 } {q 2 }
1 1 0,1
q 2 {q 2 } {q 2 } q 3 Φ {q 4 }
q 4 {q 4 } {q 4 } 下図は DFA と見なせる
{q 0 ,q 1 ,q 2 } {q 0 ,q 2 ,q 3 } {q 0 ,q 2 ,q 3 ,q 4 } {q 0 ,q 1 }
0
0 1 1
下図は DFA と見なせる
{q 0 }
0 1 2 0 2 3 0 2 3 4
0 1
0
0
0 0
0 0
1 1
1 1 1
{q 0 ,q 3 ,q 4 } {q 0 ,q 1 ,q 4 } {q 0 ,q 1 ,q 2 ,q 4 }
{q 0 ,q 3 } 0 0
1 1
1
1
2. 有限オートマトン (2)
証明 : NFA で受理できる言語のクラス N と、 DFA で受理できる言 語のクラス D が一致することを示す
語のクラス D が一致することを示す。
L ∈ N を受理する NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A と同じ言語を受理する DFA A ’ を次のように構成する A L と同じ言語を受理する DFA A L を次のように構成する。
} },
{ , ,
, 2 {
' Q D N D
L q F
A N
–
状態集合はA L
の状態集合Q N
の集合族–
初期状態{q N }
は‘q N
だけからなる集合’
であり、q N
ではない– δ D
とF D
を定義する必要がある。2. 有限オートマトン (2)
証明 :
L ∈ N を受理する NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A L と同じ言語を受理する DFA A L ’ を次のように構成する。
} }
{ 2
{
' Q q F
A N
– δ D
とF D
を定義する必要がある。} },
{ , ,
, 2
{ D N D
L q F
A
} ,
2
|
{
Q N
D S S S F
F N
2. 有限オートマトン (2) ( )
証明 :
L ∈ N を受理する NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A L と同じ言語を受理する DFA A L ’ を次のように構成する。
– δ D
とF D
を定義する必要がある。(2) Σ の要素 (NFA A
0 1
(1) 各時点で
(2) Σ の要素 (NFA A L への可能な入力 ;
|Σ| 通り )
Φ Φ Φ
{ } { } Φ
NFA A L の取 り得る状態の
集合
|Σ| 通り )
{q 0 } {q 0 ,q 1 } Φ
集合
(2 |Q N | 通り ) (1) の各状態におい て、 (2) の入力を与え
{q 0 ,q 1 , q k }
{…} {…} すべての状態の集合 た場合に遷移できる
…,q k }
0 1 0,1 0
0 1
(1) Φ Φ Φ
入力
2. 有限オートマトン (2)
q 0
q 1 q 3
q 2 q 4
0,1 0 0
1
(2) {q 0 } {q 0 ,q 1 } {q 0 ,q 3 }
(3) {q 1 } {q 2 } Φ
(4) { } { } { }
例
:
q 3 q 4 1 1 0,1
δ 0 1
(4) {q 2 } {q 2 } {q 2 }
(5) {q 3 } Φ {q 4 }
(6) {q } {q } {q }
現在の 状態の
集合
次の時刻に可能な 状態の集合
δ 0 1
q 0 {q 0 ,q 1 } {q 0 ,q 3 } q 1 {q 2 } Φ
(6) {q 4 } {q 4 } {q 4 }
(7) {q 0 ,q 1 } {q 0 ,q 1 ,q 2 } {q 0 ,q 3 } (8) {q 0 q 2 } {q 0 q 1 q 2 } {q 0 q 2 q 3 }
集合 (2 |Q| 通り )
状態の集合
q 2 {q 2 } {q 2 } q 3 Φ {q 4 }
(8) {q 0 ,q 2 } {q 0 ,q 1 ,q 2 } {q 0 ,q 2 ,q 3 }
…
(32) {q 0 ,q 1 ,q 2 ,q 3 ,q 4 } {q 0 ,q 1 ,q 2 , q 4 } {q 0 ,q 2 ,q 3 ,q 4 } q 4 {q 4 } {q 4 }
{q 0 ,q 1 ,q 2 } {q 0 ,q 2 ,q 3 } {q 0 ,q 2 ,q 3 ,q 4 } {q 0 ,q 1 }
0
0 1 1
( ) {q 0 ,q 1 ,q 2 ,q 3 ,q 4 } {q 0 ,q 1 ,q 2 , q 4 } {q 0 ,q 2 ,q 3 ,q 4 }
{q 0 }
0 1 2 0 2 3 0 2 3 4
0 1
0
0
0 0
0 0
1 1
1 1 1
{q 0 ,q 3 ,q 4 } {q 0 ,q 1 ,q 4 } {q 0 ,q 1 ,q 2 ,q 4 }
{q 0 ,q 3 } 0 0
1 1
1
1
2. 有限オートマトン (2) ( )
証明 : NFA で受理できる言語のクラス N と、 DFA で受理できる言 語のクラス D が一致することを示す。
語のクラス D が 致することを示す。
L ∈ N を受理する NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A と同じ言語を受理する DFA A ’ を次のように構成する A L と同じ言語を受理する DFA A L を次のように構成する。
} },
{ , ,
, 2 {
' Q D N D
L q F
A N
–
状態集合はA L
の状態集合の集合族–
初期状態{q N }
は‘q N
だけからなる集合’
であり、q N
ではない と 定義方法は前述 通り– δ D
とF D
の定義方法は前述の通り。証明すべきこと： δ N (q N ,w) ∩ F N ≠Φ である必要十分条件は
^
^
δ D ({q N },w) ∈ F D
⇒ |w| に関する帰納法で、計算の同等性を証明する。 ( 省略 )
^
2. 有限オートマトン (2)
2.5. ε- 動作を含む有限オートマトン (ε-NFA)
– 「入力」として「空文字 」 ε 」を許す。つまり入力を読まずに 」 状態を変化することを許す。
例 : 「 0 でない整数」
1. 最初は「＋」か「ー」か何もない
ε
を使わずに自然 な表現をするの2. 次は 1 ～ 9 が 1 つ
は困難3. それ以降は 0 ～ 9 が 0 個以上続く
は困難
＋
,
ー,ε 1,2,…,9
0,1,2,…,9
, , ,9
2. 有限オートマトン (2)
2.5. ε- 動作を含む有限オートマトン (ε-NFA)
例 :
1. まず a が 0 個以上続き、
2. 次に 次に [b [ が が 個以 0 個以上 ] ] または または [c [ が が 個以 0 個以上 ] ] 続き、 続き、
3. 最後に d が 0 個以上続く ε
を使わずに自然 な表現をするのb
は困難ε d
b
は困難a ε
c
ε ε ε
2. 有限オートマトン (2)
2.5. ε- 動作を含む有限オートマトン (ε-NFA)
– ε-NFA A=(Q,Σ,δ,q,F) の定義： 定義
• Q ：状態集合
• Σ: アルファベット
• δ: Q × Σ ∪ {ε} → 2 Q
• q: 初期状態 初期状態
• F: 受理状態
NFA A によ て受理される言語 – ε-NFA A によって受理される言語 …
• δ の定義 ??
^
2. 有限オートマトン (2)
2. 5. ε-NFA と DFA の等価性
証明 : ε-NFA で受理できる言語のクラス N と、 DFA で受理で きる言語のクラス D が一致することを示す。
• D ⊆ N
は定義より明らかなので、N ⊆ D
を示せばよい。•
任意の言語L ∈ N
がL ∈ D
となることを示せばよい。ある言語 L が L N であ たとする このとき L を受理す ある言語 L が L ∈ N であったとする。このとき、 L を受理す る ε-NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A と同じ言語を受理する DFA A ’ を構成する A L と同じ言語を受理する DFA A L を構成する。
Subset 構成において、 ε- 遷移をどう処理するか
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
Subset 構成において、 ε- 遷移をどう処理するか …
直感的には「 で移動できる状態たち を同 視すれば OK ? 直感的には「 ε で移動できる状態たち」を同一視すれば OK…?
→ それほど自明でない：
a
ε ε b
ε ε
ε
ε d
c
a ε
b
ε c
ε ε
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
Subset 構成において、 ε- 遷移をどう処理するか … 状態 の 閉包とは 状態 から 遷移だけで遷移で 状態 q の ε- 閉包とは、状態 q から ε- 遷移だけで遷移で きる状態の集合 (q 自身も含む )
ECLOSE(q) := { q’ | q’ は q から ε- 遷移だけで遷移できる } 1 q は ECLOSE(q) の要素
1. q は ECLOSE(q) の要素
2. 任意の q’ ∈ ECLOSE(q) に対して、 q’ から q’’ に ε- 遷 移で遷移できるなら、 q’’ も ECLOSE(q) の要素
移で遷移できるなら、 q も ECLOSE(q) の要素
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
Subset 構成において、 ε- 遷移をどう処理するか … 状態 の 閉包とは 状態 から 遷移だけで遷移で 状態 q の ε- 閉包とは、状態 q から ε- 遷移だけで遷移で きる状態の集合 (q 自身も含む )
ECLOSE(q) := { q’ | q’ は q から ε- 遷移だけで遷移できる }
例：
b
q 1
ε d
a ε
例：
ECLOSE(q 0 )={q 0 ,q 1 ,q 2 ,q 3 } ECLOSE(q 1 )={q 1 ,q 3 }
q 0 q 3
q 2 c
ε ε
ECLOSE(q 2 )={q 2 ,q 3 }
ECLOSE(q 3 )={q 3 }
ECLOSE(q 3 ) {q 3 }
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
Subset 構成において、 ε- 遷移をどう処理するか … 観測 NFA A において ECLOSE( ) に状態 が 観測 : ε-NFA A において、 ECLOSE(q) に状態 p が 入っているとき、「 A がある時点で取りえる状態」の集 合 S は [q ∈ S かつ p ב S ] はありえない
合 S は、 [q ∈ S かつ p ב S ] はありえない。
⇒ ε-NFA A において、「 A がある時点で取りうる状態」
の集合 S は、 q ∈ S なら ECLOSE(q) ⊆ S 。
構成において Q がすべて現れるわけでは
⇒ Subset 構成において 2 Q がすべて現れるわけでは
ない。
2. 有限オートマトン (2)
2.5.4. 遷移関数の拡張と ε-NFA の言語
( )
– ε-NFA A=(Q,Σ,δ,q,F) の定義：
• δ: Q
×Σ ∪ {ε} → 2 Q
受 される言語
状態
q
に入力xa
が 与えられたときに– ε-NFA A によって受理される言語 …
• δ:Q
×(Σ ∪ {ε}) * →2 Q
の定義: 1 δ( ) ECLOSE( )
^
^
与えられたときに 到達可能なすべて
の状態の集合
1. δ(q,ε) := ECLOSE(q)
2. δ(q,xa) (
ただしx ∈ Σ * , a ∈ Σ):
– δ(q,x) = {p 1 ,p 2 ,…,p k }
とする。k
^
^ (q, ) {p
1 ,p 2 , ,p k }
とする。–
和集合 を{r 1 ,r 2 ,…,r m }
とする。 m ECLOSE ( )
) ˆ (
k
i
i a p
1
) , ˆ (
j
r j
xa q
1
) ( ECLOSE :
) ,
(
19/25
– A によって受理される言語
L(A) := { w | δ(q,w)∩F≠Φ} ^
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
証明 : ε NFA で受理できる言語のクラス N と DFA で受理で 証明 : ε-NFA で受理できる言語のクラス N と、 DFA で受理で
きる言語のクラス D が一致することを示す。
• D ⊆ N
は定義より明らかなので、N ⊆ D
を示せばよい。•
任意の言語L ∈ N
がL ∈ D
となることを示せばよい。ある言語 L が L ∈ N であったとする。このとき、 L を受理す る ε NFA A =(Q Σ δ q F ) が存在する
る ε-NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A L と同じ言語を受理する DFA A L ’ を構成する。
構成 お 遷移をどう処理するか Subset 構成において、 ε- 遷移をどう処理するか …
ECLOSE を使って遷移可能
な状態の集合を表現する
な状態の集合を表現する
2. 有限オートマトン (2)
2. 5. ε-NFA と DFA の等価性
証明 : ある言語 L が L ∈ N であったとする。このとき、 L を受 証明 : ある言語 L が L ∈ N であったとする。このとき、 L を受
理する ε-NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A L と同じ言語を受理する DFA A L ’ =(Q D ,Σ,δ D ,q D ,F D ) を構 成す
成する。
1. Q D : 2 Q N だと無駄が多い。以下を満たす S だけで十分。
2 q : ECLOSE(q )
S q
q S
ECLOSE( )
与えられた
ε-NFA
から2. q D := ECLOSE(q N )
3. F D := { S ∈ Q D | S ∩ F N ≠Φ}
4 δ
動的に作ればよい。
4. δ D …
2. 有限オートマトン (2)
2. 5. ε-NFA と DFA の等価性
証明 ある言語 L が L ∈ N であ たとする このとき L を 証明 : ある言語 L が L ∈ N であったとする。このとき、 L を
受理する ε-NFA A L =(Q N ,Σ,δ N , q N , F N ) が存在する。
A L と同じ言語を受理する DFA A L ’ =(Q D Σ δ D q D F D ) を A L と同じ言語を受理する DFA A L (Q D ,Σ,δ D ,q D ,F D ) を 構成する。
4. δ D : Q D の要素 S と Σ の要素 a に対して、以下の手 順で構成する。
1. S = {p 1 ,p 2 ,…,p k } とする。
2 k の結果を { } とする
2. の結果を {r 1 ,r 2 ,…,r m } とする。
3
i
i a p
1
) , (
m
3. ( S , a ) : ECLOSE( r )
2. 有限オートマトン (2) ( )
2. 5. ε-NFA と DFA の等価性
例
例 : '
q 1
ε d
b
a ε
ECLOSE(q 0 )={q 0 ,q 1 ,q 2 ,q 3 } ECLOSE(q 1 )={q 1 ,q 3 }
q 0 q 3
q 2 c
ε ε
(q 1 ) {q 1 ,q 3 } ECLOSE(q 2 )={q 2 ,q 3 } ECLOSE(q )={q } ECLOSE(q 3 )={q 3 }
上記の ε-NFA と等価な DFA A=(Q,{a,b,c,d},δ,q,F) を構成
( ) { }
• q = ECLOSE(q 0 )={q 0 ,q 1 ,q 2 ,q 3 }
• δ(q,b): なので、 δ(q,b) = ECLOSE(q 1 )={q 1 ,q 3 }
• 同様に
q q
i
i
